#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

typedef unsigned long long ULL;

//if failed return 0
ULL sieve(ULL n)
{
	char *a = malloc(n+1);
	if(!a) return 0;
	memset(a,0,n+1);
	ULL max = sqrtl(n);
	ULL p = 2;
	while(p <= max){
		for(ULL i=2*p;i<=n;i+=p)
			a[i] = 1;
		while(a[++p]); /* empty */
	}
	while(a[n]) n--;
	return n;
}

int main(int argc,char **argv)
{
	ULL n = 0;
	if(argc < 2){
		printf("usage %s n\n",argv[0]);
		return 1;
	}
	sscanf(argv[1],"%llu",&n);
	if(n == 0){
		puts("wrong number format");
		return 2;
	}
	else if((long long)n < 0){
		puts("must + number");
		return 3;
	}

	int start = clock();
	ULL result = sieve(n);
	if(!result){
		puts("sieve calc failed!");
		return 4;
	}
	double end = ((1.0 * (clock() - start)) / CLOCKS_PER_SEC) * 1000.0;
	printf("max p is %llu (take %f ms)\n",result,end);
	return 0;
}
